<!DOCTYPE html>
<html>
<head>
  <title></title>
</head>
<body>
<script type="text/javascript">

  function ArrayList () {
    var array = [];

    var swap = function (array, index1, index2) {
      var aux = array[index1];

      array[index1] = array[index2];
      array[index2] = aux;
    }

    this.insert = function(item) {
      array.push(item);
    }

    // 冒泡排序
    this.bubbleSort = function() {
      var length = array.length;

      for (var i = 0; i < length; i++) {
        for (var j = 0; j < length - 1; j++) {
          if (array[j] > array[j+1]) {
            swap(array, j, j+1);
          }
        }
      }
    }

    // 冒泡排序 优化版本
    this.modifiedBubbleSort = function () {
      var length = array.length;

      for (var i = 0; i < length; i++) {
        for (var j = 0; j < (length - 1 - i); j++) { // 排除掉已经计算过的 length - 1 - i
          if (array[j] > array[j+1]) {
            swap(array, j, j+1);
          }
        }
      }
    }

    // 选择排序O(n2)
    this.selectionSort = function() {
      var length = array.length,
        indexMin;

      for (var i = 0; i < (length-1); i++) {
        indexMin = i;
        for (var j = i; j < length; j++) {
          if (array[indexMin] > array[j]) {
            indexMin = j;
          }
        }
        if (i !== indexMin) {
          swap(array, i, indexMin);
        }
      }
    }

    // 插入排序
    this.insetionSort = function () {
      var length = array.length,
        j, temp;

      for (var i =0; i < length; i++) {
        j = i;
        temp = array[i];
        while (j > 0 && array[j - 1] > temp) {
          array[j] = array[j - 1];
          j--;
        }
        array[j] = temp;
      }
    }

    // 归并排序
    var mergeSortRec = function (array) {
      var length = array.length;
      if (length === 1) {
        return array;
      }

      var mid = Math.floor(length / 2),
        left = array.slice(0, mid),
        right = array.slice(mid, length);

      return merge(mergeSortRec(left), mergeSortRec(right));
    }

    var merge = function (left, right) {
      var result = [],
        il = 0,
        ir = 0;

      while (il < left.length && ir < right.length) {
        if (left[il] < right[ir]) {
          result.push(left[il++])
        } else {
          result.push(right[ir++])
        }
      }

      while (il < left.length) {
        result.push(left[il++])
      }

      while (ir < right.length) {
        result.push(right[ir++])
      }

      return result;
    }

    this.mergeSort = function() {
      array = mergeSortRec(array);
    }

    this.toString = function() {
      return array.join();
    }
  }

  function createNonSortedArray(size) {
    var array = new ArrayList();

    for (var i = size; i > 0; i--) {
      array.insert(parseInt(Math.random() * 10));
    }

    return array;
  }

  var array = createNonSortedArray(6000);
  console.log(array.toString())
  // array.modifiedBubbleSort();
  // array.selectionSort();
  // array.insetionSort()
  array.mergeSort()
  console.log(array.toString())
</script>
</body>
</html>